FIG. 1 illustrates the operation of packet forwarding using longest prefix match forwarding tables on two prior art commercially available physically separate routers 11 and 12 connected by link 101. Router 12 has three interfaces if-1, if-2, and if-3 (respectively 121–123), and router 11 has two interfaces if-1 and if-2 (respectively 111 and 112). Each of routers 11 and 12 has respective packet forwarding table 13, 14 containing prefixes that include an IP network number and a mask length. For example, a prefix 10/8 is equivalent to an IP network number 10.0.0.0 with a mask length of 8 bits, such that only the first 8 bits of that IP network number are significant. Within packet forwarding tables 13, 14 are sets of these prefixes, for example, 10/8. Each prefix is associated with forwarding information, sometimes called “next-hop information.” The forwarding information consists, in this case, of just the interface through which the packet is forwarded.
Router 11, for example, has an entry in forwarding table 13 having prefix 10/8 and associated next-hop information Interface if-2. Accordingly, if Router 11 receives a packet through any of its interfaces, it reads the IP destination address in the header of that packet and performs what is called a longest prefix match lookup in forwarding table 13. A longest prefix match lookup finds the longest prefix in forwarding table 13 that matches the packet IP destination address. For example, if a packet destination IP address is 10.1.1.1, where each of the values between the dots is a byte or an octet, and where each octet is 8 bits, clearly the prefix 10/8 matches the first 8 bits of the IP address.
On the other hand, a packet with IP destination address 13.2.3.4 does not match the first entry in forwarding table 13, because the first 8 bits do not match. The longest prefix match must match the most significant bits in the forwarding table 13. For example, with a packet IP destination address 10.1.1.1, the longest prefix match in forwarding table 13 is 10.1.1/24, because it has more significant bits that match this destination IP address than does 10/8. However, an entry like 10.2.2/24 would not match 10.1.1.1.
Assume for example that router 12 has prefix entry 10.1/16 with a next-hop of interface if-1, and prefix entry of 10.2/16 with a next-hop of interface if-2, in forwarding table 14. Then if Router 11 receives a packet with IP destination 10.1.1.1, router 11 will perform a longest prefix match in forwarding table 13 and will find a 10.1.1/24 entry that tells it to forward that packet out through interface if-2, where it will be received by router 12. Router 12 then performs the same longest prefix match in forwarding table 14. In this case, 10.1.1.1 IP destination on the packet it receives would match the 10.1/16 entry in forwarding table 14, which tells it to forward that packet out through interface if-1 on its way to the designated destination.
If router 11 receives a packet with, for example, IP destination 10.2.2.5, then router 11 would match that to 10.2.2/24 in its forwarding table and forward the packet out through interface if-2, where it would be received by router 12. Router 12 would do a lookup and would match the packet to 10.2/16, where it would forward the packet out through interface if-2.